#
# @lc app=leetcode.cn id=322 lang=python3
#
# [322] 零钱兑换
#

# @lc code=start
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [-1 for _ in range(amount + 1)]
        dp[0] = 0
        for i in range(1, amount + 1):
            l = []
            for j in coins:
                if i - j >= 0 and dp[i - j] != -1:
                    l.append(dp[i - j] + 1)
            if l:
                dp[i] = min(l)
        return dp[amount]
# @lc code=end

